/**
 * @author 03010570
 * @date 2020/07/01
 * describe:    LeetCode:   718、最长重复子数组 https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/
 */
public class LeetCode_718 {
    public static void main(String[] args) {
        int[] ints1 = {1, 2, 3, 2, 1};
        int[] ints2 = {3, 2, 1, 4, 7};
        System.out.println(findLength3(ints1, ints2));
        ints1 = new int[]{0, 0, 0, 0, 1};
        ints2 = new int[]{1, 0, 0, 0, 0};
        System.out.println(findLength3(ints1, ints2));
    }

    public static int findLength3(int[] A, int[] B) {
        int[] dp = new int[B.length + 1];
        int max = 0;
        for (int i =1; i <= A.length; i++) {
            for (int j = B.length; j >= 1; j--) {
                dp[j] = A[i - 1] == B[j - 1] ? dp[j - 1] + 1 : 0;
                if (dp[j] > max) {
                    max = dp[j];
                }
            }
        }
        return max;

    }

    /**
     * 一维数组 ： 只会有一列有值
     * dp :
     * if(a[i]==b[j])
     * dp[j] = [j-1] +1;
     *
     * @param A
     * @param B
     * @return
     */
    public static int findLength2(int[] A, int[] B) {
        if (A.length == 0 || B.length == 0) {
            return 0;
        }
        int[] dp = new int[B.length + 1];
        int max = 0;
        for (int i = 1; i <= A.length; i++) {
            for (int j = B.length; j >= 1; j--) {
                if (A[i - 1] == B[j - 1]) {
                    dp[j] = dp[j - 1] + 1;
                } else {
                    dp[j] = 0;
                }
                max = Math.max(max, dp[j]);
            }
        }
        return max;

    }

    /**
     * DP: 二维数组
     * dp[i][j];
     * 递推公式： dp[i][j] = a[i] == b[j] ? dp[i-1][j-1] +1 : 0;
     *
     * @param A
     * @param B
     * @return
     */
    public static int findLength(int[] A, int[] B) {
        if (A.length == 0 || B.length == 0) {
            return 0;
        }
        int[][] dp = new int[A.length + 1][B.length + 1];
        int max = 0;
        for (int i = 1; i <= A.length; i++) {
            for (int j = 1; j <= B.length; j++) {
                if (A[i - 1] == B[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = 0;
                }
                max = Math.max(max, dp[i][j]);
            }
        }
        return max;

    }
}
